#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>

//单链表的结点定义
typedef int DataType;
typedef struct Node
{
    DataType data;
    struct Node * next;
}Node;
//单链表的初始化
Node* InitList()
{
    Node * first = (Node *)malloc(sizeof(Node));
    first->next = NULL;
    return first;
}
//判空操作
int Empty(Node * first)
{
    if (first->next == NULL) return 1;
    else return 0;
}
//遍历操作
void PrintList(Node * first)
{
    Node * p = first->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}
//求单链表的长度
int Length(Node * first)
{
    Node * p = first->next;
    int count = 0;
    while (p != NULL)
    {
        p = p->next;
        count++;
    }
    return count;
}
//按值查找
int Locate(Node * first, DataType x)
{
    Node * p = first->next;
    int count = 1;
    while (p != NULL)
    {
        if (p->data == x) return count;
        p = p->next;
        count++;
    }
    return 0;
}
//按位查找
int Get(Node * first, int i, DataType * ptr)
{
    Node * p = first->next;
    int count = 1;
    while (p != NULL && count < i)
    {
        p = p->next;
        count++;
    }
    if (p == NULL) { printf("位置错误,查找失败\n"); return 0; }
    else { * ptr = p->data; return 1; }
}
//插入操作
int Insert(Node * first, int i, DataType x)
{
    Node * s = NULL, * p = first;
    int count = 0;
    while (p != NULL && count < i - 1)
    {
        p = p->next;
        count++;
    }
    if (p == NULL) { printf("位置错误,插入失败\n"); return 0; }
    else
    {
        s = (Node *)malloc(sizeof(Node));
        s->data = x;
        s->next = p->next; p->next = s;
        return 1;
    }
}
//建立单链表头插法
Node* CreaList(DataType a[], int n)
{
    Node * s = NULL;
    Node * first = (Node *)malloc(sizeof(Node)); first->next = NULL;
    for (int i = 0; i < n; i++)
    {
        s = (Node *)malloc(sizeof(Node));
        s->data = a[i];
        s->next = first->next; first->next = s;
    }
    return first;
}
//建立单链表尾插法
Node *CreatList(DataType a[], int n)
{
    Node * s = NULL, * r = NULL;
    Node * first = (Node *)malloc(sizeof(Node));
    r = first;
    for (int i = 0; i < n; i++)
    {
        s = (Node *)malloc(sizeof(Node));
        s->data = a[i];
        r->next = s; r = s;
    }
    r->next = NULL;
    return first;
}
//删除操作
int Delete(Node * first, int i, DataType * ptr)
{
    Node * p = first, * q = NULL;
    int count = 0;
    DataType x;
    while (p != NULL && count < i - 1)
    {
        p = p->next;
        count++;
    }
    if (p == NULL || p->next == NULL)
    {
        printf("位置错误,删除失败\n");
        return 0;
    }
    else
    {
        q = p->next; * ptr = q->data;
        p->next = q->data;
        free(q); return 1;
    }
}
//销毁单链表
void DestroyList(Node * first)
{
    Node * p = first;
    while (first != NULL)
    {
        first = first->next;
        free(p);
        p = first;
    }
}
//单链表的使用
int main()
{
    int r[5] = { 1,2,3,4,5 }, i, x;
    Node * first = NULL;
    first = CreatList(r, 5);
    printf("当前线性表的数据为:");
    PrintList(first);
    Insert(first, 2, 8);
    printf("执行插入操作后数据为:");
    PrintList(first);
    printf("当前单链表的长度为:%d", Length(first));
    printf("请输入查找的元素值:");
    scanf("%d", &x);
    i = Locate(first, x);
    if (i != 0) printf("元素%d的元素位置为:%d\n", x, i);
    else printf("单链表中没有元素%d\n", x);
    printf("请输入要删除第几个元素:");
    scanf("%d", &i);
    if (Delete(first, i, &x) == 1)
    {
        printf("删除的元素值是%d,执行删除操作后数据为: ", x);
        PrintList(first);
    }
    else printf("删除操作失败\n");
    DestroyList(first);
    return 0;
}
